class PoolBalancing
	def self.balance(values, nbpools)
		values.sort! { |a,b| b[0] <=> a[0] }
		pools = Array.new( nbpools ) { Array.new }
		poolsum = Array.new( nbpools, 0 )
		out = Array.new

		ind = 0; dir = 1
		values.each do |val|
			pools[ind] << val
			poolsum[ind] += val[0]
			ind += dir;
			if( ind == nbpools ) then ind = nbpools-1; dir = -1; end
			if( ind == -1 ) then ind = 0; dir = 1; end
		end

		while out.length < (nbpools-1)
			minmax = poolsum.each_with_index.minmax.map{ |t| t[1] }
			diff = poolsum[minmax[1]] - poolsum[minmax[0]]
			return pools.map { |p| p.map { |v| v[1]  }  } if diff <= 1 && out.empty?

			ind = 0
			delete = true
			while ind < pools[minmax[1]].length && delete == true
				maxval = pools[minmax[1]][ind][0]
				minval = pools[minmax[0]][ind][0]

				if (poolsum[minmax[1]] - 2 * maxval + 2 * minval - poolsum[minmax[0]]).abs < diff
					pools[minmax[1]][ind][0] = minval
					pools[minmax[0]][ind][0] = maxval
					poolsum[minmax[1]] += (minval - maxval)
					poolsum[minmax[0]] += (maxval - minval)
					delete = false
					pools.concat(out.pop) && out.clear unless out.empty?
				end
				ind+=1
			end

			out << pools.delete_at(minmax[0]) if delete
		end
	end
end